0903. DI 序列的有效排列【困难】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 解法 1

1. 📝 题目描述

• leetcode

给定一个长度为 n 的字符串 s，其中 s[i] 是:

• “D” 意味着减少，或者
• “I” 意味着增加

有效排列 是对有 n + 1 个在 [0, n] 范围内的整数的一个排列 perm，使得对所有的 i：

• 如果 s[i] == 'D'，那么 perm[i] > perm[i+1]，以及；
• 如果 s[i] == 'I'，那么 perm[i] < perm[i+1]。

返回 有效排列 perm的数量。因为答案可能很大，所以请返回你的答案对 10^9 + 7 取余。

---

示例 1：

输入：s = "DID"
输出：5
解释：
(0, 1, 2, 3) 的五个有效排列是：
(1, 0, 3, 2)
(2, 0, 3, 1)
(2, 1, 3, 0)
(3, 0, 2, 1)
(3, 1, 2, 0)

示例 2：

输入: s = "D"
输出: 1

---

提示：

• n == s.length
• 1 <= n <= 200
• s[i] 不是 'I' 就是 'D'

2. 🎯 s.1 - 解法 1

js

// todo

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$